package com.sourcetrip.raw.adt.abs;


import com.sourcetrip.raw.model.MyBinaryNode;

/**
 * @author: ZhouBert
 * @date: 2020/12/1
 * @description: Balanced Binary Search Tree
 * 自平衡的二叉搜索树
 * 为了抽取 AVL-Tree 和 RB-Tree 的公共方法
 */
public abstract class MyAbstractBBST<E extends Comparable> extends MyAbstractBinarySearchTree<E> {


	/**
	 * 在查找的基础上，我们做添加
	 * 根据分析：添加可能会导致父节点失衡，最坏情况将导致祖先节点失衡直至根节点
	 *
	 * @param element
	 */
	@Override
	public void add(E element) {
		size++;
		if (root == null) {
			root = createNode(element, null);///new MyBinaryNode<>(element, null);
			afterAdd(root);
			//默认将 guard 的 left 指向 root
//			guard.setLeft(root);
			return;
		}
		//找到 pNode - 父节点，先进行添加
		MyBinaryNode<E> pNode = node(element, root);
		if (pNode.getElement().compareTo(element) > 0) {
			if (pNode.getLeft() != null) {
				pNode.getLeft().setElement(element);
			} else {
				//pNode.setLeft(new MyAVLNode<>(element, pNode));
				pNode.setLeft(createNode(element, pNode));
				afterAdd(pNode.getLeft());
			}
		} else if (pNode.getElement().compareTo(element) < 0) {
			if (pNode.getRight() != null) {
				pNode.getRight().setElement(element);
			} else {
				///pNode.setRight(new MyAVLNode<>(element, pNode));
				pNode.setRight(createNode(element, pNode));
				afterAdd(pNode.getRight());
			}
		} else {
			throw new RuntimeException("unexpected in add()!");
		}
	}

	/**
	 * 移除
	 * 这里不能用 guard 节点！因为 rotate 会影响 guard 的定位
	 * -- 如果要用的话，必须得在旋转之后重定位一下 guard
	 * @param element
	 */
	@Override
	public void remove(E element) {
		if (size == 0) {
			throw new RuntimeException("没有元素可以用于删除！");
		}
		MyBinaryNode<E> cur = this.root;
		MyBinaryNode<E> prev = null;
		while (cur != null) {
			if (cur.getElement().compareTo(element) == 0) {
				break;
			}
			prev = cur;
			if (cur.getElement().compareTo(element) > 0) {
				cur = cur.getLeft();
			} else {
				cur = cur.getRight();
			}
		}

		if (cur == null) {
			//没有找到元素--> 直接返回
			return;
		}
		//找到元素--> 进行删除
		//1.如果找到的是头节点，先统一处理，避免代码太突兀了！
		//region	没有利用 guard 的版本
		if (prev == null && !(cur.getLeft() != null && cur.getRight() != null)) {
			if (cur.getLeft() == null && cur.getRight() == null) {
				root = null;
			} else if (cur.getLeft() != null) {
				root = cur.getLeft();
				root.setParent(null);
			} else if (cur.getRight() != null) {
				root = cur.getRight();
				root.setParent(null);
			}
			return ;
		}
		//endregion

		//2.接下来就可以不用考虑头节点了
		//但是使用了 哨兵节点，考虑一下写法
		if (cur.getLeft() == null && cur.getRight() == null) {
			if (prev.getLeft() == cur) {
				prev.setLeft(null);
			} else {
				prev.setRight(null);
			}
			size--;
			//afterRemove(cur);
			// 由于 红黑树需要用被替代的节点的颜色进行判断，所以这里多传了一个参数
			afterRemove(cur, null);
		} else if (cur.getLeft() != null && cur.getRight() == null) {
			if (prev.getLeft() == cur) {
				prev.setLeft(cur.getLeft());
			} else {
				prev.setRight(cur.getLeft());
			}
			//修复子的 parent
			cur.getLeft().setParent(prev);
			size--;
			//afterRemove(cur);
			afterRemove(cur, cur.getLeft());
		} else if (cur.getRight() != null && cur.getLeft() == null) {
			if (prev.getLeft() == cur) {
				prev.setLeft(cur.getRight());
			} else {
				prev.setRight(cur.getRight());
			}
			cur.getRight().setParent(prev);
			size--;
			//afterRemove(cur);
			afterRemove(cur, cur.getRight());
		} else {
			//两个节点都有
			MyBinaryNode<E> predecessor = cur.getLeft();
			while (predecessor.getRight() != null) {
				predecessor = predecessor.getRight();
			}
			//此时找到了 前驱节点
			//先删除 前驱节点
			remove(predecessor.getElement());
			cur.setElement(predecessor.getElement());
		}
	}

	/**
	 * 找到 element 元素的父节点
	 * 1.找到元素时：找到的元素的 父节点；
	 * 2.未找到元素时：该放置位置的 父节点；
	 *
	 * @param element
	 * @param root
	 * @return
	 */
	protected MyBinaryNode<E> node(E element, MyBinaryNode<E> root) {
		if (root == null) {
			return null;
		}
		// 如果不为 null
		MyBinaryNode<E> cur = root;
		MyBinaryNode<E> prev = null;
		while (cur != null) {
			if (cur.getElement().compareTo(element) == 0) {
				break;
			}
			prev = cur;
			if (cur.getElement().compareTo(element) > 0) {
				cur = cur.getLeft();
			} else if (cur.getElement().compareTo(element) < 0) {
				cur = cur.getRight();
			}
		}
		return prev;
	}

	//region	钩子方法

	/**
	 * 创建一个新的节点
	 *
	 * @param ele
	 * @param parent
	 * @return
	 */
	protected MyBinaryNode<E> createNode(E ele, MyBinaryNode<E> parent) {
		return new MyBinaryNode<>(ele, parent);
	}

	/**
	 * @param newNode 新添加的节点
	 */
	protected void afterAdd(MyBinaryNode<E> newNode) {
	}

	/**
	 * 删除节点
	 * @param deletedNode	被删除的节点（通过保留对 parent 的引用来实现调整）
	 */
	protected void afterRemove(MyBinaryNode<E> deletedNode, MyBinaryNode<E> replaceNode) {

	}



	//endregion


}
